In modern digital data processing systems, a desired data processing task typically is accomplished by the selective execution of a plurality of procedures. In such an arrangement, each procedure is a sequence of executable instructions that performs a specific processing subtask and the collection of procedures that is employed collectively defines the instruction set required for the system to accomplish the particular desired data processing task. As is known in the art, in any given process, the procedures are not necessarily executed sequentially. For example, to accomplish a particular subtask, a procedure may invoke ("call") one or more additional procedures which perform a portion of the subtask and, upon execution of the called procedure, either return control and execution to the calling procedure or transfer control and execution to yet another procedure. As also is known in the art, one or more of the procedures utilized in carrying out a particular data processing task can be invoked and executed a number of times before the desired result is obtained.
Using a collection of procedures to define a processing task has well known advantages from the standpoint of memory overhead (i.e., minimizing the amount of system memory required for execution of the process). In addition, using a collection of procedures has well-known advantages from the standpoint of reducing the complexity of programming the digital data processing system. For example, with regard to procedures that are executed a number of times, (i.e., repeated at various execution points of a process), only a single instruction set for the procedure need be stored in system memory and invoked as needed. This not only reduces the amount of memory required for storing coded instructions, but also decreases system complexity from the programming standpoint. Specifically, virtually all high level programming languages allow the system programmer to write a program that includes procedure declarations and procedure calls that respectively create procedures and allow a created procedure to be invoked and executed at desired points of the computer program. This not only eliminates copying of the procedure instructions at various points of the program, but allows the programmer to create programs that can be used again in other processes. That is, the programmer can create "program parts" for various tasks that are not uniquely related to the digital data processing task at hand.
Use of program parts and separate procedures to define processes for execution by digital data processing systems has resulted in the availability of numerous programs and procedures which are of general application and, therefore, can be incorporated as procedures in various data processing situations. In this regard, it has become widespread practice to utilize available programs and procedures as program parts that are loaded into the data processing system through conventional input/output devices and to prepare and load any additional program parts that are required in order to define a desired process. Further, many digital data processing systems include one or more libraries that include various procedures of general application, with the libraries being resident in system memory. The procedures of such libraries can be invoked and executed on an as needed basis in response to procedure calls that are included in program parts that are loaded into the system by the system user.
In order for a digital data processing system to transfer control and execution to another procedure or access data that is required during execution of a procedure, the system must be able to locate the storage location of the procedure being invoked or the storage location of the data being accessed. The simplest and earliest technique for locating another procedure or data consists of including in the instructions of a procedure the specific memory address of the procedure or data. Alternatively the procedure can include instructions for calculating the required address based on some other specific memory address. Successful execution of this type of code will not occur unless the digital data processing system loads the procedures to be invoked and the data to be accessed at particular, predetermined memory addresses that are dictated by the code. Because of the dependency upon loading of data and processes at specific memory addresses, this type of code sometimes is called position dependent code.
The use of position dependent code can present a substantial drawback, especially in situations in which a large number of procedures are employed or access to a large number of data sets is required. Specifically, memory space must be dedicated at code dictated addresses for storage of the procedures that might be invoked during a process and memory space also must be dedicated for storage of all data sets that might be accessed during execution of the process. In many situations, the procedures employed during a process (and the data accessed) will depend upon conditions that are determined and events that occur during execution of the process. Using position dependent code in such a situation means that procedure and data will occupy memory space even though the procedures are never invoked and the data is never accessed during execution of the process. More important, situations exist in which the memory address of data that is to be executed or procedures that are to be invoked are not known at the time at which the procedures that will access the data or invoke the other procedures are loaded into system memory. Of primary consideration in this regard is the dynamic loading of procedures such as shared library procedures that are not brought into the process until the library procedure is referenced (called during execution of previously loaded procedures). Since the memory address at which a dynamically loaded procedure will be stored cannot be determined until the procedure is brought into the process, position dependent code cannot successfully invoke such procedure.
To overcome the above-discussed drawbacks and disadvantages, various position independent code techniques have been developed that allow the system to access data and invoke procedures that are loaded into portions of memory that are not preassigned or identified until the data to be accessed and/or the procedures to be invoked are loaded for execution. This not only allows dynamic loading of shared library procedures and data, but also can result in a substantial reduction in memory overhead. Moreover, because position independent code includes no references to specific memory addresses, the code can be used to establish procedures in processes other than the process for which the code is written. Further, using procedures that employ position independent code can be a distinct advantage in situations such as data processing systems that perform concurrent (parallel) processing. For example, in a parallel processing environment any particular procedure may be concurrently invoked and executed by more than one processing unit and some of the procedures may be invoked and executed several times. If position dependent code is utilized in such procedures, it may be difficult (or even impossible) to store data accessed by the procedure and/or procedures that are called by the procedure at code dictated memory locations for each concurrent use of the procedure.
Both hardware devices and software systems have been developed to facilitate the use of position independent code in digital data processing systems. Although satisfactory in many situations, prior art hardware devices increase both the cost and complexity of the data processing system. Prior art systems that utilize only software also are satisfactory in many situations, but these systems also have distinct disadvantages and drawbacks. For example, one prior art system is limited to digital data processing systems that maintain a program counter in a general register of the central processing unit. In that type of arrangement, the position independent code that is used to access data that is external to the procedure or to call a different procedure includes instructions for adding a specific offset value to the current value of the program counter to thereby generate an address at which the data to be accessed or procedure to be invoked must be stored. In some instances, the address generated by adding the offset value to the current value of the program counter is not the memory address of the data or procedure, but is an address in memory at which the address of the procedure or data can be found.
The primary drawback of prior art position independent code that utilizes and relies upon a general register program counter is inefficiency, both with respect to minimizing the amount of memory space required for execution of a process and with respect to attaining minimum execution time for a process. Accordingly, a need exists for improved methods of providing position independent code.